package com.yuan.algorithms.分治算法;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

/**
 * ForkJoin分治算法
 * 分治思想结合多线程技术，加速整体任务的完成速度
 * @author YouYuan
 * @date 2022/3/12 21:38
 */
public class ForkJoinTest {

    // 单次处理数据量
    private static final int TASK_NUM = 10000;
    private static final int DATA_SIZE = 10000000;

    private static class JoinTask extends RecursiveTask<Long> {

        // 任务列表
        private final List<Long> taskList;
        private final int from;
        private final int to;

        public JoinTask(List<Long> taskList, int from, int to) {
            this.taskList = taskList;
            this.from = from;
            this.to = to;
        }

        @Override
        protected Long compute() {
            if (to - from <= 0) {
                return null;
            }
            long childSum = 0;
            if (to - from <= TASK_NUM) {
                for (int i = from; i < to; i++) {
                    childSum += taskList.get(i);
                }
                return childSum;
            } else {
                /**
                 * 拆分子任务，提交给forkJoin执行，分而治之
                 */
                try {
                    // 模拟任务切换用时
                    Thread.sleep(5);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                int mid = (to + from) >> 1;
                JoinTask leftJoinTask = new JoinTask(taskList, from, mid);
                JoinTask rightJoinTask = new JoinTask(taskList, mid, to);
                invokeAll(leftJoinTask, rightJoinTask);
                return leftJoinTask.join() + rightJoinTask.join();
            }
        }
    }
    public static void main(String[] args) {
        // 初始化任务数据
        List<Long> taskList = new ArrayList();
        for (int i = 0; i < DATA_SIZE; i++) {
            taskList.add(i + 1L);
        }

        // 普通方法计算
        long start = System.currentTimeMillis();
        long computeSum = plainCompute(taskList, 0, taskList.size());
        long end = System.currentTimeMillis();
        System.out.println("plainCompute:" + computeSum + ", use time:" + (end-start));

        // forkJoin 计算
        long startF = System.currentTimeMillis();
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        JoinTask joinTask = new JoinTask(taskList, 0, taskList.size());
        Long result = forkJoinPool.invoke(joinTask);
        long endF = System.currentTimeMillis();
        System.out.println("forkJoinTask:" + result + ", use time:" + (endF-startF));

    }

    private static long plainCompute(List<Long> taskList, int from, int to) {
        if (to - from <= TASK_NUM) {
            long sum = 0;
            for (int i = from; i < to; i++) {
                sum += taskList.get(i);
            }
            return sum;
        } else {
            try {
                // 模拟任务切换用时
                Thread.sleep(25);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            int mid = (from + to) >> 1;
            return plainCompute(taskList, from, mid) + plainCompute(taskList, mid, to);
        }
    }
}
